//dfs
/**131.分割回文子串
 * 输入：s = "aab"
   输出：[["a","a","b"],["aa","b"]]
 */

var partition = function(s) {
    let res = [];
    const isPalindrome = (s,l,r)=>{
        while(l<=r){
            if(s[l]!==s[r]) return false;
            l++;r--;
        }
        return true;
    }

    const traverse = (track,start)=>{
        if(start === s.length){
            res.push([...track]);
            return;
        }
        for(let j=start;j<s.length;j++){
            let w = s.substring(start,j+1);
            if(isPalindrome(s,start,j)){
                track.push(w);
                traverse(track,j+1);
                track.pop();
            }
        }
    }
    traverse([],0);
    return res;
};